Skip to main content

Linked Lists

A linked list is a data structure that, similar to an array, stores elements in an ordered sequence. The main difference is that linked lists are made up of objects called ListNodes (nodes).

A ListNode is an object that contains two attributes:

  1. value - this stores the value of the node. It could be a character, an integer, another object, anything, etc.
  2. next - this stores the reference to the next node (the next node’s address in memory) in the linked list.

→ this is the way to connect multiple ListNodes together.

1. Creating a Linked List​

By chaining these ListNode objects together we can build a linked list.

class ListNode:
    def __init__(self, val):
        self.val = val      # the actual value
        self.next = None    # reference to the next node

Example: We have three ListNode objects - ListNode1, ListNode2, ListNode3.

In this example:

  • value attribute is a string - red, blue, green.
  • We need to make sure that our next pointers point to another ListNode, and not null. Only the last node in the linked list would have its next pointer point to null.
ListNode1.next = ListNode2
ListNode2.next = ListNode3
ListNode3.next = null

When we instantiate a list node, we don’t know where it is stored in memory. The nodes likely won’t be contiguous like arrays, but this isn’t an issue for linked list.

2. Traversal​

To traverse a linked list from beginning to end, we can make use of a while loop.

  • We start the traverse at the head of the list, ListNode1.
  • We assign it to a variable current, denoting the current node we are at.
  • We execute the while loop until we each the end of the list, which is null.
  • In each iteration, we update current to be the next node in the list by setting current = current.next. → The traversal runs in O(n) time where n is the number of nodes in the linked list.
current = ListNode1
while cur:
    current = current.next

3. [Circular Linked List](https://www.youtube.com/watch?v=clh4QgiXjlc​

If ListNode3’s next pointer is set to ListNode1 instead of null, this results in a circular linked list. Attempting to iterate through a circular linked list would result in an infinite loop.

I. Singly Linked Lists​

1. Appending Operations​

An advantage that linked lists have over arrays is that inserting a new element can be performed in O(1) time, even if we insert in the middle.

  • We do not have to shift any elements since there is no requirement for the elements to be stored contiguously in memory.

This assumes that we’d already have a reference to the node at the desired position we want to insert. If we have to traverse the list to arrive at the insertion point, the operation would take O(n) time.

Example: If we wanted to append ListNode4 to the end of the list, we would be appending to the tail.

  • Once ListNode4 is appended, we update our tail pointer to be ListNode4. → This operation would be done in O(1).
tail.next = ListNode4
tail = ListNode4

2. Deleting from a Singly Linked List​

Deleting a node from a singly linked list will take O(1) since we can accomplish this by updating a single pointer, again, we’re assuming we have a reference to the node at the desired position we want to delete.

Example: We want to delete ListNode2.

  • Currently, our head points to ListNode1, and head.next points to ListNode2.
  • We can update head.next pointer to ListNode3, by chaining next pointers like head.next.next.
head.next = head.next.next

It can be assumed that the memory occupied by ListNode2 will be cleared via garbage collection in most languages. In other languages like C, you would have to manually free the memory.

Summary​

Time Complexity​

II. Doubly Linked List​

A node in a doubly linked list now has two pointers, in addition to the next pointer, we have a prev pointer which points to the previous node. If prev points to null, that means we’re at the head of the linked list.

class ListNode: 
  def init(self, val = 0, next = None, prev = None): 
    self.val = val
    self.next = next
    self.prev = prev

1. Insert Operations​

a. Insertion End​

Similar to the singly linked list, adding a node to a doubly linked list will run in O(1) time. Only this time, we have to update the prev pointer as well.

Example: We have three nodes in our linked list, ListNode1, ListNode2, ListNode3. If we want to insert at the end another node, ListNode4, we will have to update both the next pointer of ListNode3 and the prev pointer of the new node, ListNode4.

tail.next = ListNode4
ListNode4.prev = tail
tail = tail.next

b. Insertion Front​

To add a node to the head of a doubly linked list:

  1. We update the next pointer of the new node ListNode4 to the current head - ListNode1.
  2. We update the prev pointer of ListNode1 to the new node - ListNode4.
ListNode4.next = head 
head.prev = ListNode4

2. Delete Operations​

a. Deletion End​

Deleting at the end is also a O(1) operation:

  1. First we get a reference to the node before the tail.
  2. We update the next pointer of the node before the tail to null.
  3. We update the tail to be the node before the tail.
  4. (Optional) We can also update the prev pointer of the old tail to null.
# get the node before tail
ListNode2 = tail.prev

# set this node's next pointer to null
ListNode2.next = null 
tail = ListNode2 # ListNode2 becomes the new tail

b. Deletion Front​

To delete a head node:

  1. We get the reference to the second node (right after the head).
  2. We update the second node’s prev pointer to null
head.next.prev = null
head = head.next # new head of the linked list

3. Access​

Similar to singly linked lists, we cannot randomly access a node. So in the worst case, we will have to traverse n nodes before reaching the desired node. This would run in O(n) time.

Doubly linked lists have the benefit that we can traverse the list in both directions, as opposed to singly linked lists.

Summary​

Time Complexity​

III. Queues​

Queues are the reverse of stacks, they follow a FIFO approach (First in First Out).

A real world example would be a line at the bank. The first person added to the line (queue) is the first person to be served.

The easiest way to implement a queue is using a linked list. It is also possible to implement a queue using a dynamic array, but is more involved.

The main two operations that queues support are enqueue and dequeue.

1. Enqueue​

The enqueue operation inserts an element to the end of the queue. If we implement this operation with a singly linked list it runs in O(1) time.

def enqueue(self, val):
    newNode = ListNode(val)

    # Queue is non-empty
    if self.right:
        self.right.next = newNode
        self.right = self.right.next
    # Queue is empty
    else:
        self.left = self.right = newNode

2. Dequeue​

The dequeue operation removes an element from the front of the queue and returns that element.

It is a good measure to check if the queue is empty before performing the dequeue operation.

def dequeue(self):
    # Queue is empty
    if not self.left:
        return None
    
    # Remove left node and return value
    val = self.left.val
    self.left = self.left.next
    if not self.left:
        self.right = None
    return val

There is also a variation of the queue, a double-ended queue, known as a deque (pronounced "deck"). A deque allows you to add and remove elements from both the head and the tail in O(1) time.